15.2-1
$A_1 : 5 \times 10$,
$A_2 : 10 \times 3$,
$A_3 : 3 \times 12$,
$A_4 : 12 \times 5$,
$A_5 : 5 \times 50$,
$A_6 : 50 \times 6$.
Then an optimal parenthesization is $((A_1 A_2)((A_3 A_4)(A_5 A_6)))$.
15.4-1
$X = [1,0,0,1,0,1,0,1]$
$Y = [0,1,0,1,1,0,1,1,0]$
$LCS = [1,0,0,1,1,0]$
15.4-3
Algorithm:
LCS-Length($X$, $Y$):
$m := X.length$
$n := Y.length$
let $c[0 ... m][0 ... n]$ be new table
for $i$ from $0$ to $m$:
$c[i][0] := 0$
for $j$ from $0$ to $n$:
$c[0][j] := 0$
for $i$ from $1$ to $m$:
for $j$ from $1$ to $n$:
$c[i][j] := - \infty$
Return Maintain-Table($X$, $Y$, $c$, $m$, $n$)
Maintain-Table($X$, $Y$, $c$, $i$, $j$):
if $i$ == $0$ or $j$ == $0$:
Return $0$
if $c[i-1][j]$ == $- \infty$:
$c[i-1][j] :=$ Maintain-Table($X$, $Y$, $c$, $i-1$, $j$)
if $c[i][j-1]$ == $- \infty$:
$c[i][j-1] :=$ Maintain-Table($X$, $Y$, $c$, $i$, $j-1$)
if $c[i-1][j-1]$ == $- \infty$:
$c[i-1][j-1] :=$ Maintain-Table($X$, $Y$, $c$, $i-1$, $j-1$)
if $X[i]$ == $Y[j]$:
Return $c[i-1][j-1] + 1$
else:
Return $\max( c[i-1][j], c[i][j-1] )$
Analysis:
Firstly, observe that LCS-Length contains two for-loops with $O(m)$, $O(n)$ time complexity and one nested for-loop with $O(mn)$ time complexity. Next, with the boundary condition, it's not difficult to see that the recursive times of Maintain-Table will not exceed the size of table $c$, ie. $(m+1)(n+1)$. And Maintain-Table consumes $O(1)$ execution time except recursive function call. Hence, the initial call of Maintain-Table consumes $O(mn)$ execution time, thus LCS-Length's time complexity is $O(mn) + O(mn) = O(mn)$.
15.4-5
Design:
LIS($A$):
$n := A.length$
let $d[1 ... n]$, $b[1 ... n]$ be new arrays
$m := 0$
for $i$ from $1$ to $n$:
$d[i] := 1$
$b[i] := -1$
for $i$ from $1$ to $n$:
for $j$ from $1$ to $i-1$:
if $A[j] < A[i]$ and $d[j] >= d[i]$:
$d[i] := d[j] + 1$
$b[i] := j$
if $d[i] > d[m]$:
$m := i$
let $r[1 ... d[m]]$ be new array
$i := d[m]$
while $m != -1$:
$r[i] := A[m]$
$m := b[m]$
$i := i - 1$
Return r
Correctness:
First of all, we are gonna prove that $d[i]$ maintains the longest length of increasing subsequence(LIS) ended at $i$. $(*)$
It suffices to see the nested for-loop, and we will use loop invariant to prove it.
Loop Invariant (for the outer for-loop of the nested for-loop):
At the start of $i$-th iteration, $(*)$ holds for all $k < i$.
Initialization:
When the first iteration starts, $d[1 ... k-1]$ is empty. The loop invariant is true obviously.
Maintenance:
Suppose the loop invariant is true when $i$-th iteration starts. Observe that, if the LIS ended at some $k < i$ and has length $d[k]$, then the LIS ended at $i$ must be the LIS ended at some $k$ appending $A[i]$ and have length $d[k]+1$. So the inner for-loop guarantees $(*)$ holds for $i$, then the loop invariant is true when $(i+1)$-th iteration of outer for-loop starts. Note that if the conditional statement is not triggered for all $1 \leq j \leq i-1$, then $d[i]$ keeps the default value $1$ does make sense.
Termination:
As our discussion in Maintenance part, $(*)$ holds for $i$ == $n$ when the final iteration ends up. Therefore, the loop invariant makes $(*)$ holds for all $1 \leq i \leq n$.
When $(*)$ is proved, $b[i]$ maintains the previous term of the LIS ended at $i$ is clear. And $m$ indicates the end index of the LIS till now is also clear. Then, it's not difficult to realize the construction of LIS in the while-loop.
Analysis:
All non-constant time operation:
Construction of $d$ and $b$: $O(n)$
First for-loop: $O(n)$
Second for-loop: Since $i \leq n$, the inner for-loop is of $O(n)$, then the nested for-loop is $O(n^2)$
Construction of $r$: $O(n)$ (because $d[m] \leq n$)
While-loop: $O(n)$ (because $i$ == $0$ $\iff$ $m$ == $-1$)
Hence, the time complexity of LIS is $O(n^2)$.
15.5-1
Given $n$ and table $root$.
Construct-Optimal-BST($root$):
$r := root[1][n]$
print( 'k' + $r$ + ' is the root' )
Construct-Optimal-SubBST($root$, $1$, $r-1$, 'left', $r$)
Construct-Optimal-SubBST($root$, $r+1$, $n$, 'right', $r$)
Construct-Optimal-SubBST($root$, $i$, $j$, $direction$, $parent$):
if $i \leq j$:
$r := root[i][j]$
print( 'k' + $r$ + ' is the ' + direction + ' child of k' + $parent$ )
Construct-Optimal-SubBST($root$, $i$, $r-1$, 'left', $r$)
Construct-Optimal-SubBST($root$, $r+1$, $j$, 'right', $r$)
else:
if $direction$ == 'left':
print( 'd' + $(parent-1)$ + ' is the left child of k' + $parent$ )
else:
print( 'd' + $parent$ + ' is the right child of k' + $parent$ )